package com.LeeCode;

/**
 * 最小化两个数组中的最大值
 */

public class Code2513 {
    public static void main(String[] args) {
        System.out.println(new Code2513().lcm(2, 7));
        System.out.println(new Code2513().check(4, 2, 7, 1, 3));
    }

    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        int left = 0, right = Integer.MAX_VALUE;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {
                right = mid;
            } else
                left = mid;
        }
        return right;
    }

    private boolean check(long x, int d1, int d2, int c1, int c2) {
        // 计算不能被 d1 整除的数的数量
        long total1 = x - x / d1;
        if (total1 < c1) return false;

        // 计算不能被 d2 整除的数的数量
        long total2 = x - x / d2;
        if (total2 < c2) return false;

        // 计算不能被 d1 或 d2 整除的总数量（可用作互不重叠）
        long lcm = lcm(d1, d2);
        long common = x - x / lcm;
        return common >= c1 + c2;
    }

    // 求最小公倍数 LCM = a*b / GCD(a,b)
    private long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    // 求最大公约数
    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
